import java.util.ArrayDeque;
import java.util.Queue;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
public class project {
    public boolean isEvenOddTree(TreeNode root) {
        Queue<TreeNode> queue=new ArrayDeque<>();
        int len=-1;
        if(root!=null){
            queue.add(root);
            while (!queue.isEmpty()){
                int size=queue.size();
                len++;
                int prevVal=0;
                for(int i=0;i<size;i++){
                    TreeNode tmp=queue.poll();
                    if(tmp.left!=null){
                        queue.add(tmp.left);
                    }
                    if(tmp.right!=null){
                        queue.add(tmp.right);
                    }
                    if(i==0){
                        prevVal=tmp.val;
                        if(len%2==0&&prevVal%2==0){
                            return false;
                        }
                        if(len%2==1&&prevVal%2==1){
                            return false;
                        }
                    }else{
                        if(len%2==0){
                            if(tmp.val%2==0||tmp.val<=prevVal){
                                return false;
                            }
                        }else{
                            if(tmp.val%2==1||tmp.val>=prevVal){
                                return false;
                            }
                        }
                        prevVal=tmp.val;
                    }
                }
            }
        }
        return true;
    }
}
